package algorithm.middle;

import javax.swing.text.html.parser.Entity;
import java.util.*;

/**
 * 所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
 * <p>
 * 编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/repeated-dna-sequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindRepeatedDnaSequences187 {
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() <= 10) {
            return new ArrayList<>();
        }
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            String str = s.substring(i, i + 10);
            map.put(str, map.getOrDefault(str, 0) + 1);
        }
        ArrayList<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                list.add(entry.getKey());
            }
        }
        return list;
    }

    /*哈希表 滑动窗口 位运算
    https://leetcode-cn.com/problems/repeated-dna-sequences/solution/zhong-fu-de-dnaxu-lie-by-leetcode-soluti-z8zn/
     */

    int ten = 10;
    //00 01 10 11
    Map<Character,Integer> map = new HashMap<Character,Integer>(){{
       put('A',0);
       put('C',1);
       put('G',2);
       put('T',3);
    }};

    public List<String> findRepeatedDnaSequences2(String s) {
        int len = s.length();
        if (len<=10){
            return new ArrayList<>();
        }
        int x = 0;
        //x代表窗口的所有字符转成的二进制数字
        for (int i=0;i<ten-1;i++){
            x = (x << 2)|map.get(s.charAt(i));
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        ArrayList<String> ans = new ArrayList<>();
        for(int i=0;i+ten<=len;i++){
            //右加入两位，20位左边置空
            x =  ((x << 2)|map.get(s.charAt(i+ten-1)))&((1<<20)-1);
            hashMap.put(x,hashMap.getOrDefault(x,0)+1);
            if (hashMap.get(x)==2){
                ans.add(s.substring(i,i+ten));
            }
        }
        return ans;
    }
}
